(Problem) 005 Smallest multiple

Project Euler

• 공식 홈페이지 - projecteuler.net
• 한글 번역 - projecteuler @kr
• (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Problem list

• No 5 : Smallest multiple
  • HackerRank : Project Euler #4: Smallest multiple

Smallest multiple

problem <번역>

solution

Simple Code

최소 공배수를 찾는 문제이다.
최대 공약수, 최소 공배수를 찾을 때 유클리드 호제법을 응용한 유클리드 알고리즘을 사용하면 쉽다.

005_smallest_multiple.py

def gcd(a, b):
  while b > 0:
      a, b = b, a % b

  return a


def lcd(a, b):
  return a * b // gcd(a, b)


def smallest_multiple(n):
  cur = 1

  for num in range(1, n+1):
      cur = lcd(cur, num)

  return cur


print(smallest_multiple(20))  

---

HackerRank

테스트 케이스 입력 받는 부분만 추가해 주면 된다.

005_for_HacerRank.py

def gcd(a, b):
  while b > 0:
      a, b = b, a % b

  return a


def lcd(a, b):
  return a * b // gcd(a, b)


def smallest_multiple(n):
  cur = 1

  for num in range(1, n+1):
      cur = lcd(cur, num)

  return cur


if __name__ == '__main__':
  for _ in range(int(input())):
      print(smallest_multiple(int(input()))) 

유클리드 호제법을 잘 이해하고 있다면 쉽게 풀 수 있는 문제이다.